# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 3.make_the_change.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/11/23 9:49
------------------------------------------
凑零钱问题
    有 k种面值的硬币，面值分别为 c1, c2, ..., ck,
    每种硬币的数量无限，再给一个总金额 count，
    问：最少需要几枚硬币凑出这个金额？如果凑不出，返回-1

解析：这个问题是动态规划问题，因为它具有「最优⼦结构」的。要符合 「最优⼦结构」，⼦问题间必须互相独⽴。
    ⽐如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（⼦问题），
    你只需要把⼦问题的答案加⼀（再选⼀枚⾯值为 1 的硬币） 就是原问题的答案，因为硬币的数量是没有限制的，⼦问题之间没有相互制，是互相独⽴的

思路：
    1.先确定「状态」，也就是原问题和⼦问题中变化的变量。由于硬币数量⽆ 限，所以唯⼀的状态就是⽬标⾦额 amount
    2.然后确定 dp函数的定义：当前的⽬标⾦额是 n ，⾄少需要 dp(n) 个硬 币凑出该⾦额
    3.然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态
    4.最后明确 base case，显然⽬标⾦额为 0 时，所需硬币数量为 0；当⽬标⾦额 ⼩于 0 时，⽆解，返回 -1
"""


# 1. 暴力递归
def coin_change(coins: list, amount: int):
    def dp(n):
        if n == 0:
            return 0

        if n < 0:
            return -1

        # 求最小值，所以初始化为正无穷
        res = float('INF')

        for coin in coins:
            sub_problem = dp(n - coin)

            # 子问题无解，跳过
            if sub_problem == -1:
                continue

            res = min(res, 1 + sub_problem)

        return res if res != float('INF') else -1

    return dp(amount)


def coin_change_with_memo(coins: list, amount: int):
    """
        改进，带备忘录，避免重复计算
    """
    memo = dict()

    def dp(n):
        # 查备忘录，避免重复
        if n in memo:
            return memo[n]

        elif n == 0:
            return 0

        elif n < 0:
            return -1

        res = float('INF')
        for coin in coins:

            sub_problem = dp(n - coin)
            if sub_problem == -1:
                continue

            res = min(res, 1 + sub_problem)

        memo[n] = res if res != float('INF') else -1

        return memo[n]

    return dp(amount)


def coins_change_with_dp_table(coins: list, amount: int):
    """
        dp数组迭代法,这里在Python中，使用 dict比较合适
        自底向上消除重叠子问题
    """
    dp = {x: amount + 1 for x in range(amount + 1)}

    # dp[x] = y，表示当目标金额为 x时，至少需要 y枚硬币
    dp[0] = 0

    # todo 到这儿了，该理解理解了
    for i in range(len(dp)):
        # 内层for 求所有子问题 + 1的最小值

        for coin in coins:
            # 子问题无解，跳过
            if i - coin < 0:
                continue

            part_key = i - coin

            # 这里为啥用min? 因为初始的dp[i]为amount + 1，也就是比全是1块的硬币数 大1，是当做正无穷用的，不是正确解，比最大正确解还多1
            # 其次，这里把每种币值作为第一个硬币或者说首次减去的硬币的方案都试过，已经存在的dp[i]值可能也可以凑出所求总值，但是币不是最少的

            # 这里为什么总是1+xxx？这里的1代表被减去的币的数量，即 i - coin中 coin的数量，不管币值是多少，减去的都是1个硬币，所以一直是1 +xx
            dp[i] = min(dp[i], 1 + dp[part_key])

    return -1 if dp[amount] == amount + 1 else dp[amount]


if __name__ == '__main__':
    coins = [1, 2, 5]
    amount = 11
    # print(coin_change(coins, amount))
    # print(coin_change_with_memo(coins, amount))
    print(coins_change_with_dp_table(coins, 11))
